#leetcode题目22：括号生成
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n)
#方法：回溯
from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n==0:
            return []
        res=[]
        self.backtrack(n,0,0,"",res)
        return res
    def backtrack(self,n,left,right,path,res):
        if len(path)==2*n:
            res.append(path)
            return
        if left<n:
            self.backtrack(n,left+1,right,path+"(",res)
        if right<left:
            self.backtrack(n,left,right+1,path+")",res)



#测试数据
n=3
#预期输出：["((()))","(()())","(())()","()(())","()()()"]
solution=Solution()
print(solution.generateParenthesis(n))



